package com.xieyong.leetcode;

public class Leetcode3201 {
    public static void main(String[] args) {
        Leetcode3201 leetcode3201 = new Leetcode3201();
        int[] nums = {1,1,7,3,2};
        int i = leetcode3201.maximumLength(nums);
        System.out.println(i);

    }

    public int maximumLength2(int[] nums) {
        int ans = 0;
        int[][] dp = new int[2][2];
        for (int num : nums) {
            num %= 2;
            dp[0][num] = dp[num][0] + 1;
            dp[1][num] = dp[num][1] + 1;
            ans = Math.max(ans, Math.max(dp[0][num], dp[1][num]));
        }
        return ans;
    }

    public int maximumLength(int[] nums) {
        int n = nums.length;
        int[][] dplist = new int[4][n + 1];
        int ouIndex = -1, jiIndex = -1;
        for (int i = 0; i < n; i++) {
            if (nums[i] % 2 == 0) {
//                找到上一个偶数
                if (ouIndex != -1) {
                    dplist[0][i + 1] = dplist[0][ouIndex + 1] + 1;
                }else {
                    dplist[0][i + 1] = 1;
                }
//                找到上一个奇数
                if (jiIndex != -1) {
                    dplist[2][i + 1] = dplist[2][jiIndex + 1] + 1;
                    dplist[3][i + 1] = dplist[3][jiIndex + 1] + 1;
                } else {
                    dplist[2][i + 1] = 1;
                }
                ouIndex = i;
            } else {
//                找到上一个奇数
                if (jiIndex != -1) {
                    dplist[1][i + 1] = dplist[1][jiIndex + 1] + 1;
                } else {
                    dplist[1][i + 1] = 1;
                }
//                找到上一个偶数
                if (ouIndex != -1) {
                    dplist[2][i + 1] = dplist[2][ouIndex + 1] + 1;
                    dplist[3][i + 1] = dplist[3][ouIndex + 1] + 1;
                }else {
                    dplist[3][i + 1] = 1;
                }
                jiIndex = i;
            }
//            如果没有操作过，则沿用左边的结果
            for (int j = 0; j < 4; j++) {
                if (dplist[j][i + 1] == 0) {
                    dplist[j][i + 1] = dplist[j][i];
                }
            }
        }

        return Math.max(Math.max(dplist[0][n], dplist[1][n]),Math.max(dplist[2][n], dplist[3][n]));
    }
}
